# -*- coding=utf-8 -*-
# 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合
# candidates 中的数字可以无限制重复被选取

# 说明：
# 所有数字（包括 target）都是正整数
# 解集不能包含重复的组合

# 示例 1:
# 输入: candidates = [2,3,6,7], target = 7,
# 所求解集为:
# [
#   [7],
#   [2,2,3]
# ]

# 示例 2:
# 输入: candidates = [2,3,5], target = 8,
# 所求解集为:
# [
#   [2,2,2,2],
#   [2,3,3],
#   [3,5]
# ]

# class Solution(object):
#     def combinationSum(self, candidates, target):
#         """
#         :type candidates: List[int]
#         :type target: int
#         :rtype: List[List[int]]
#         """
#         candidates.sort();
#         return self.combinationSumIndex(candidates, target, 0);

#     def combinationSumIndex(self, candidates, target, index):
#         rtn = [];
#         if index > len(candidates) - 1:
#             return rtn;
#         if target < candidates[index]:
#             return rtn;

#         for i in xrange(index, len(candidates)):
#             value = candidates[i];
#             signal = [];
#             while target >= value:
#                 signal.append(value);
#                 target -= value;
#                 if target == 0:
#                     rtn.append(signal);
#                     break;
#                 part_result = self.combinationSumIndex(candidates, target, i + 1);
#                 if len(part_result) == 0:
#                     continue;
#                 for part in part_result:
#                     part.extend(signal);
#                     part.sort();
#                     rtn.append(part);
#             target = sum(signal) + target;

#         return rtn;








# 查看运行最快的解法，思路相同，但是写法更简洁，特别是把中间过程通过path传递到下一层调用
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort();

        rtn = [];
        def rpc(remain, path):
            if remain == 0:
                rtn.append(path);
                return;
            for v in candidates:
                if v > remain:
                    break;
                if path and v < path[-1]:
                    continue;
                rpc(remain - v, path + [v]);

        rpc(target, []);
        return rtn;





t = Solution();
print t.combinationSum([2,3,5], 8);